第1章 超标量处理器概览

1.1 为什么需要超标量

程序执行时间 = $Instructions * CPI * f$。其中:$Instructions$指的是指令个数，$CPI$(Cycles per Instrution)指的是执行每条指令所需的周期数，$f$指的是每周期所需要的时间，亦即时钟频率。

加快处理器执行程序的速度

可以考虑以下三点：

• 减少程序中指令的数量。指令的数量对已经编写好的固定程序是定值。

• 减少CPI，即增大IPC（Instructions per Cycle，每周期执行指令的个数）。

  普通流水线处理器的IPC最大为1。要想每周期执行多于一条指令，就需要使用超标量（Superscalar）处理器。

  处理器采用何种架构进行实现也成为微结构（Microarchitecture）。

• 减少周期时间（cycle time），即加大频率。

  • 精巧的电路设计，更深的流水线
  • 优秀的EDA工具
  • 硅工艺

实际中IPC与运行频率是互相制约的。

超长指令字（Very Long Instruction Word，VLIW）也是一种每周期可以执行多条指令的处理器架构。

• 超标量处理器依靠硬件自身决定哪些指令可被并行地执行，VLIW处理器依靠编译器和程序员自身来决定。
• VLIW在硬件实现上简单，在功能专一的专用处理器领域得到应用，如DSP。

处理器设计需要折中（tradeoff）

• 分支预测
  • 精确的分支预测算法需要复杂的硬件资源，无法在一个周期内完成
  • 分支预测无法在一个周期内完成，那么处理器就不能连续地取指令，造成性能下降
• load/store指令
  • 完全乱序执行可获得较大的IPC。
  • 相关性检查变得复杂，需要更复杂的恢复机制。
• Checkpoint的个数与硬件的面积
• 发射队列（issue queue）的个数与仲裁（select）电路的复杂度
• 每周期可同时执行的指令个数（issue width）和寄存器堆（register file）的端口个数

超标量处理器设计没有一个确定的设计原则，需要根据应用领域和场合确定设计的思路。

1.2 普通处理器的流水线

1.2.1 流水线概述

这里假设处理器的性能与处理器的频率直接相关。

在现实中，频率并不是决定处理器性能的唯一因素。

当处理器没有使用流水线时，周期时间为D，消耗的硬件面积为G。

对于一个 $n$ 级流水线，周期时间变为 $\frac{D}{n} + S$，其中S表示流水线寄存器的延迟；消耗的硬件面积为 $G + n * L$，其中L为每个流水线寄存器及其附属的控制逻辑所消耗的硬件面积。

$n$ 级流水线处理器的性能（Performance） = $\frac{1}{\frac{D}{n}+S}$；总共消耗的硬件面积（Cost） = $G + n * L$。

获得同样的性能，消耗的硬件面积越小越好，用公式表示为：

$$
\frac{Cost}{Performance} = \frac{G + n * L}{\frac{1}{\frac{D}{n}+S}} = \frac{GD}{n} + nSL + LD + GS
$$
对上式求导可得到函数的极值点，由此可以得到最优化的流水线级数n。

现实设计中根据实际需求得到理想的流水级级数。

1.2.2 流水线的划分

1. 每个阶段所需要的时间近似相等

   最长的流水段所需要的时间决定了整个处理器的周期时间

2. 每个阶段的操作都会被重复地执行

3. 每个阶段的操作都和其他的流水段相互独立、互不相干

   最难满足，也是影响执行效率的关键因素

不同的指令集，流水线实现的难易程度是不同的。

对于一般的精简指令集（RISC）来说，如MIPS和ARM，由于指令的长度相等，并且每条指令所完成的任务比较规整，所以容易用流水线来实现。

经典RISC处理器的流水线如下图。

该MIPS处理器的设计在大二的计组实验中已经学习。

但是，每个流水段所需要的时间相差很多，因此需要对各个流水段进行平衡。

合：将两个或多个流水段合并成一个流水段

适用于对性能要求不高的低功耗嵌入式处理器。每个流水段所耗费的时间均衡，但整体的运行频率下降。

拆：将一个流水段拆成更小的阶段

可以获得比较高的主频，适合高性能处理器。

• 导致硬件消耗的增大
• 寄存器堆的端口数要随之增加，以支持多个流水段同时读写
• 存储器（如D-Cache）的端口数量要随之增加
• 处理器的功耗随之增大
• 神流水线导致预测失败时的惩罚（mis-prediction penalty）增大

一定范围内增加处理器的流水线深度可以提高性能。

1.2.3 指令间的相关性

先写后读（RAW）

Read After Write，也称true dependence，这种相关性是无法回避的。
$$
A: R_1 = R_2 + R_3\
B: R_5 = R_1 + R_4
$$
B的操作数$R_1$来自A的结果，所以要等待A将结果计算出来，B才能继续运行。

先读后写（WAR）

也称anti-dependence。
$$
A: R_1 = R_2 + R_3\
B: R_2 = R_5 + R_4
$$
A读取$R_2$之前，B不能把结果写入到$R_2$。

这种相关性是可以避免的，只需要B将的结果写入到其他寄存器。

先写后写（WAW）

也称output dependence。
$$
A: R_1 = R_2 + R_3\
B: R_1 = R_5 + R_4
$$
这种相关性是可以避免的，只需要B将结果写入到其他寄存器。

控制相关性

由分支指令引起。只有当分支指令的结果被计算出来的时候，才可以知道从哪里获得后续的指令来执行。

分支指令需要一段时间才能获得结果，在这段时间内只能按照预测的方式来取指令。

存储器地址的相关性

RAW，WAR，WAW三个相关性不仅对寄存器之间的关系适用，对于存储器地址之间的关系也同样适用。

如sw r1, 0(r5)和lw r2, 0(r6)两条指令，当r5与r6的值相等时，这两条指令存在RAW的相关性。

这种类型的相关性需要将load/store指令所携带的地址计算出来才可以判别。

小结

指令之间的各种相关性，使得他们在处理器中无法完全地乱序执行。

对于普通的处理器来说，WAW和WAR并不会引起问题，RAW可以通过旁路（bypass）的方式来解决。

对于超标量处理器来说，三种相关性都会阻碍指令的乱序执行，都需要在处理器中进行特殊的处理。

1.3 超标量处理器的流水线

超标量处理器的执行方式：顺序执行（in-order）和乱序执行（out-of-order）。

• Frontend：流水线的取指令（Fetch）和解码（Decode）阶段，很难实现（也没有意义）乱序执行。

• Issue：将指令送到对应的功能单元（Function Unit，FU）中执行

  这里可以实现乱序执行，只要指令的源操作数准备好了，就可以将其先于其他指令运行。

• Write back：将指令的结果写到目的寄存器中。

  在处理器内部适用寄存器重命名，将指令集中定义的逻辑寄存器（Architecture Register File，ARF）动态地转化为芯片内部实际使用的物理寄存器（Physical Register File，PRF），从而实现乱序地写回寄存器。

• Commit：一条指令被允许更改处理器的状态（Architecture state，如D-Cache等）

  为了保证程序按照原来的意图执行，并且实现精确的异常，这个阶段需要顺序执行，才能够保证从处理器外部看起来，程序是串行执行的。

1.3.1 顺序执行

若每周期可从I-Cache中取出两条指令来执行，则称为2-way的超标量处理器。

发射（Issue）：指令解码之后，读取寄存器而得到操作数，根据自身的类型，将指令送到对应的FU中执行。

所有FU要经过同样周期数的流水线，保证流水线的写回（Write back）阶段是顺序执行的。

Scoreboard

Scoreboard记录流水线中每条指令的执行情况。典型情况下需要记录的信息如下。

• P：Pending，指令的结果还没有写回到逻辑寄存器中。
• F：一条指令在哪个FU中执行，在将指令结果进行旁路的时候会使用这个信息。
• Result Position：记录一条指令到达FU中流水线的哪个阶段，3表示到达FU流水线的第一个流水段，1表示到达FU流水线的最后一个阶段，0表示到达写回阶段。

程序在顺序执行的超标量流水线中的执行情况如下图所示。

很多指令在流水线都会由于前面指令的阻塞而不能够继续执行。例如上图的指令F，它与前面的指令都是不相关的，但是这条指令只有等到前面所有的指令都已经发射了，它才可以送到FU中执行，这样就降低了处理器的性能。

在所有的处理器中，RAW相关性都是不能绕开的。

但是对于WAW和WAR，由于顺序执行的处理器只有一个统一的写回阶段，而且这个阶段位于流水线的最后一级，所以这两种相关性都不会对流水线产生影响。

1.3.2 乱序执行

一旦某条指令的操作数准备好了，就可以将其送入FU中执行。

为了在乱序执行时解决WAW和WAR这两种相关性，需要对寄存器进行重命名（register renaming），可以在解码（Decode）阶段完成，也可以单独使用一个流水段来完成。

处理器中需要增加物理寄存器堆（Physical Register File，PRF）配合对指令集中定义的寄存器（Architecture Register File，ARF）进行重命名，PRF中寄存器的数量要多于ARF。

指令在发射阶段被储存在一个缓存中，这个缓存称为发射队列（Issue Queue，IQ）。一旦操作数准备好了，就可以从发射队列中离开，送到对应的FU中执行。

发射阶段是流水线从顺序执行到乱序执行的分界点。

由于每个FU执行周期数都不相同，所以指令在写回阶段是乱序的。一条指令只要计算完毕，就会把结果写到PRF中。

分支预测失败（mis-prediction）和异常（exception）的存在使得PRF的结果未必都会写到ARF中，因此也将PRF称为Future File。

重排序缓存和提交阶段

为了保证程序的串行结果，指令需要按照程序中规定的顺序更新处理器的状态，需要使用重排序缓存（ROB）的部件来配合。使用ROB来实现程序对处理器状态的顺序更新，这个阶段称为提交（Commit）阶段。

一条指令在这个阶段会将它的结果从PRF搬移到ARF中，同时重排序缓存也会配合完成对异常的处理。

退休

如果不存在异常，那么指令就可以顺利地离开流水线，并对处理器的状态进行更改，此时称这条指令退休（retire）了。

一条指令一旦退休，就不可能回到之前的状态了。一条指令在退休之前，都可以从流水线中被清除。

Store Buffer

如果在写回阶段就将store指令的结果写到存储器中，那么一旦由于分支预测失败或是异常等原因，需要将这条store指令从流水线中抹掉时，就没有办法恢复存储器的状态。

使用一个缓存（Store Buffer，SB）来存储store指令没有退休以前的结果。store指令在写回阶段会将他的结果写到SB中，只有一条store指令真正retire之后，才可以把它的值从SB写到存储器中。

load指令除了从D-Cache中寻找数据，还需要从Store Buffer中进行查找。

程序在乱序执行的超标量流水线中的执行情况如下图所示。

i表示发射阶段；解码和寄存器重命名位于同一个流水段；r表示计算完成，在ROB中等待retire；C表示一条指令经过了提交阶段，离开流水线而退休了，这个过程是按照程序中规定的顺序（in-order）执行的。